﻿
namespace Leetcode.N1140;
public class Solution
{
    public int StoneGameII(int[] piles)
    {
        var ans = new (int sum, int count)[piles.Length][];
        var sums = new int[piles.Length + 1];
        sums[0] = 0;
        for (int i = 1; i < sums.Length; i++)
        {
            sums[i] = sums[i - 1] + piles[i - 1];
        }
        var mCount = piles.Length;
        for (int i = piles.Length - 1; i >= 0; i--)
        {
            ans[i] = new (int sum, int count)[mCount];

            for (int m = 0; m < piles.Length; m++)
            {
                if (i + (m + 1) * 2 >= piles.Length)
                {
                    ans[i][m] = (sums[piles.Length] - sums[i], piles.Length - i);
                }
                else
                {
                    (int sum, int count) r = (0, 0);
                    for (int k = 0; k < (m + 1) * 2; k++)
                    {
                        var nextIndex = i + 1 + k;

                        var sum1 = sums[nextIndex] - sums[i];
                        var sum2 = 0;

                        var nextM = Math.Max(m, k);
                        var next = ans[nextIndex][Math.Min(mCount - 1, nextM)];

                        if (nextIndex + next.count < ans.Length)
                        {
                            var next2 = ans[nextIndex + next.count][Math.Min(mCount - 1, Math.Max(nextM, next.count - 1))];
                            sum2 = next2.sum;
                        }

                        if (sum1 + sum2 >= r.sum)
                        {
                            r = (sum1 + sum2, k + 1);
                        }
                    }
                    ans[i][m] = r;
                }
            }
        }
        return ans[0][0].sum;
    }
}